#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<numeric>
using namespace std;

class Solution{
    public:
    //out of time
    int ans1(vector<int>& gas, vector<int>& cost){
        int gas_total = 0, cost_total = 0;
        int length = gas.size();
        for(int i = 0; i != length; i++){
            gas_total += gas[i];
            cost_total += cost[i];
        }
        if(gas_total < cost_total){
            return -1;
        }
        int my_gas = 0;
        int index;
        int place;
        for(int i = 0; i != length; i++){
            if(gas[i] >= cost[i]){
                my_gas = 0;
                place = 0;
                for(int j = 0; j != length; j++){
                    index = (j+i) % length;
                    my_gas = my_gas + gas[index] - cost[index];
                    if(my_gas < 0){
                        break;
                    }
                    place++;
                }         
            }
            if(place == length){
                return i;
            }else{
                i = i + place + 1;
            }
        }
        return -1;
    }

    int ans2(vector<int>& gas, vector<int>& cost){
        int length = size();
        int index, i = 0;
        while(i < length){
            int my_gas = 0;
            int j = 0;
            while(j < length){
                int index = (i+j) % length;
                my_gas = my_gas + gas[index] - cost[index];
                if(my_gas < 0){
                    break;
                }
                j++;
            }
            if(j == length){
                return i;
            }
            else{
                i = i + j + 1;      //跳过前面能走到的部分
            }
        }
        return -1;

    }

};

void test1(){
    Solution s;
    vector<int> gas = {1, 2, 3, 4, 5};
    vector<int> cost = {3, 4, 5, 1, 2};

    int index = s.ans1(gas, cost);
    cout << index << endl;
}

void test2(){
    Solution s;
    vector<int> gas = {2, 3, 4};
    vector<int> cost = {3, 4, 3};

    int index = s.ans1(gas, cost);
    cout << index << endl;
}

int main(void){
    test1();
    test2();

    return 0;
}